/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-01-15
 * Time: 23:50
 */
public class Solution {
//     思路一:
//     滑动窗口
//     若新加上一个数字后 和大于target
//     就试着让窗口的左边界变小
//     看看是否有更小的结果
     public int minSubArrayLen(int target, int[] nums) {
         int len=nums.length;
         if(len==0) return 0;
         int ans=Integer.MAX_VALUE;
         int left=0;  // 左边界
         int right=0; // 右边界
         int sum=0; // 记录窗口中的数字之和
         while(right<len){
             sum+=nums[right];
             // 和大于 target 试着缩小窗口
             while(sum>=target){
                 ans=Math.min(ans,right-left+1);
                 sum-=nums[left];
                 left++;
             }
             right++;
         }
         return ans==Integer.MAX_VALUE? 0:ans;
     }


//     思路二:
//     前缀和+二分查找
//     因为数组的元素是正整数, 所以前缀和递增, 可以用二分查找
//     寻找 前缀和 差值 大于等于 target 的最小间隔
    public int minSubArrayLen2(int target, int[] nums) {
        int len=nums.length;
        if(len==0) return 0;
        int ans=len+1;
        // 前缀和, 为了方便多开辟一个空间
        int[] prefix=new int[len+1];
        for(int i=1;i<=len;i++){
            prefix[i]=prefix[i-1]+nums[i-1];
        }
        // 开始利用二分查找进行计算
        for(int i=0;i<=len;i++){
            // 找 差值 >=target 的最近的一个前缀和的下标
            int temp=prefix[i]+target;
            int index=binarySearch(prefix,temp);
            // 没找到 就跳过
            if(index<1||index>len){
                continue;
            }
            // 更新最小值
            ans=Math.min(ans,index-i);
        }
        return ans==len+1?0:ans;
    }
    /**
     二分查找
     注意:
     最后arr[left]>=target
     arr[right]<target
     如果想要查找不到目标时
     返回最相近但小于 target 的就选择 left
     返回最相近但大于 target 的就选择 right
     但需要注意left right 分别是怎么变化的
     */
    public int binarySearch(int[] arr,int target){
        int left=0;
        int right=arr.length-1;
        while(left<right){
            int mid=(left+right)>>1;
            if(arr[mid]==target){
                return mid;
            }else if(arr[mid]<target){
                left=mid+1;
            }else{
                right=mid;//注意这里取大的, 对应 right!=mid-1
            }
        }
        // 如果 arr[left]<target 说明没找到 >= target 的数字
        return arr[left]>=target? left: -1;
    }
}
